package com.ly.algorithm.leetcode.linked;

import org.junit.jupiter.api.Test;

/**
 * @Classname Problem2
 * @Description TODO
 * @Date 2020/10/4 21:17
 * @Author 冷心影翼
 */
public class Problem2 {

	public static void main(String[] args) {
		Solution2 solution2 = new Solution2();
		ListNode listNode = new ListNode(1);
		ListNode listNode2 = new ListNode(9);
		listNode2.next = new ListNode(9);
		listNode2.next.next = new ListNode(9);
		listNode2.next.next.next = new ListNode(9);
		ListNode res = solution2.addTwoNumbers(listNode, listNode2);
		System.out.println(res.next.next.next.val);
	}
}

class Solution2 {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode res = new ListNode(-1);
		ListNode cur = res;
		int carry = 0;
		while (l1!=null || l2!=null) {
			int v1 = l1==null?0:l1.val;
			int v2 = l2==null?0:l2.val;
			int add = v1+v2+carry;
			cur.next = new ListNode(add%10);
			carry = add/10;
			if(l1!=null) {
				l1 = l1.next;
			}
			if(l2!=null) {
				l2 = l2.next;
			}
			cur = cur.next;
		}
		if(carry!=0) {
			cur.next = new ListNode(carry);
		}
		return res.next;
	}

	public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
		return recursive(l1, l2, 0);
	}

	private ListNode recursive(ListNode l1, ListNode l2, int carry) {
		if (l1 == null && l2 == null && carry == 0) {   // 递归结束条件
			return null;
		}
		int l1Val = l1 == null ? 0 : l1.val;
		int l2Val = l2 == null ? 0 : l2.val;
		int curSum = l1Val + l2Val + carry;
		ListNode curNode = new ListNode(curSum % 10);
		curNode.next = recursive(l1 == null ? null : l1.next, l2 == null ? null : l2.next, curSum / 10);
		return curNode;
	}

}



